# https://leetcode.cn/problems/partition-labels/description/


# 这道题关键实际上是同一个字母只能出现在一个片段，采用贪心的思想
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 初始化一个长度为26的列表（代表26字母），用于记录每个字母最后一次出现的位置（覆盖掉了）
        last = [0] * 26
        # 遍历字符串，记录每个字母最后一次出现的位置
        for i, ch in enumerate(s):
            # 下标和值拿过来
            # 这里当前字母的ASCII-a的就是这个字母是26个字母里面第几个的，i代表位置
            last[ord(ch) - ord("a")] = i

        # 初始化一个列表，用于存储分割点
        partition = list()
        # 初始化开始位置和结束位置
        start = end = 0

        # 遍历字符串
        for i, ch in enumerate(s):
            # 更新结束位置为当前字母最后一次出现的位置（这里每次都是更新最后一个字母出现的，对于当前序列来说是只有一个）
            # 对于每个序列寻找最远位置，这个MAX是为了保证序列包含同一个字母数量最大（因为是最后一次，所以一定把当前字母的所有的包含了，满足了条件1）
            # 这句代码是保证每个序列里面出现的字母在其他序列里面不会出现第二次的核心代码
            end = max(end, last[ord(ch) - ord("a")])

            # 如果当前位置等于结束位置，说明当前分割点已经找到（再没有新元素了，就可以切割了，保证条件一满足就切割，是分割点尽可能的多）
            # 这句代码就是保证切割点尽可能的多核心代码
            if i == end:
                # 将分割点长度添加到列表中
                partition.append(end - start + 1)
                # 重新开始下一个窗口
                # 更新开始位置为结束位置的下一个位置
                start = end + 1

        # 返回分割点列表
        return partition
